package com.caochenlei.search;

import java.util.Arrays;

public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90};
        System.out.println("10的index=" + fibonacciSearch(arr, 10));
        System.out.println("50的index=" + fibonacciSearch(arr, 50));
        System.out.println("90的index=" + fibonacciSearch(arr, 90));
    }

    //获取斐波那契数列
    public static int[] fib(int length) {
        int[] fibArr = new int[length];
        fibArr[0] = 1;
        fibArr[1] = 1;
        for (int i = 2; i < length; i++) {
            fibArr[i] = fibArr[i - 1] + fibArr[i - 2];
        }
        return fibArr;
    }

    //斐波那契查找算法
    public static int fibonacciSearch(int[] arr, int num) {
        int[] f = fib(arr.length);                  //获取斐波那契的数组
        int left = 0;                               //原始数组左边的下标
        int right = arr.length - 1;                 //原始数组右边的下标
        int k = 0;                                  //斐波那契数组的下标
        while (f[k] - 1 < right) {                  //指向数组的最后索引
            k++;
        }

        //由于f(k)不是步长为1的递增数列，所以可能出现f(k) - 1的值大于原始数组最后一个索引的情况
        //比如原始数组最大索引为4，那么此时f(k)就等于5，所以要构造一个新数组，不够的部分会用0填充
        //如果多余部分用0填充可能会造成查找失败，因此，需要将0的部分填充为原来数组中的最后一个元素
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arr[right];
        }


        while (left <= right) {                     //循环查找
            int mid = left + f[k - 1] - 1;          //获取mid
            if (num < temp[mid]) {                  //往左查找
                right = mid - 1;
                k -= 1;
            } else if (num > temp[mid]) {           //往右查找
                left = mid + 1;
                k -= 2;
            } else {
                return mid <= right ? mid : right;  //返回下标
            }
        }
        return -1;
    }
}
